
//662. 二叉树最大宽度
import java.util.*;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 用两个队列分别存储节点和对应的索引
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> indexQueue = new LinkedList<>();

        // 初始时，根节点入队，索引为 0
        nodeQueue.offer(root);
        indexQueue.offer(0);

        int maxWidth = 0;

        // 广度优先遍历二叉树
        while (!nodeQueue.isEmpty()) {
            int size = nodeQueue.size();
            int firstIndex = indexQueue.peek();  // 当前层的第一个节点的索引
            int lastIndex = firstIndex;  // 初始化为第一个节点的索引

            for (int i = 0; i < size; i++) {
                TreeNode node = nodeQueue.poll();
                int index = indexQueue.poll();

                // 更新当前层的最后一个节点索引
                lastIndex = index;

                // 将左右子节点入队
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    indexQueue.offer(2 * index);  // 左子节点的索引是父节点索引的 2 倍
                }
                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    indexQueue.offer(2 * index + 1);  // 右子节点的索引是父节点索引的 2 倍 + 1
                }
            }

            // 当前层的宽度是最后一个节点索引与第一个节点索引的差值 + 1
            maxWidth = Math.max(maxWidth, lastIndex - firstIndex + 1);
        }

        return maxWidth;
    }
}